package com.lsa.letcode.the109.sortedListToBst;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

import com.lsa.helpers.Utils;
import com.lsa.iview.trees.BinaryTree.Node;
import com.lsa.iview.trees.BinaryTreeUtils;
import com.lsa.letcode.common.LetCodeTestBase;
import com.lsa.letcode.common.ListNode;
import com.lsa.letcode.common.TreeNode;
import com.lsa.letcode.common.TreeUtils;

public class SortedListToBstTest extends LetCodeTestBase{
	@Test
	public void test() throws Exception {
		test(asList(1, 2, 3, 4, 5, 6, 7));
		test(asList(1, 1));
		test(asList(1, 2));
		test(asList(1, 2, 3));
		test(asList(1, 2, 3, 4));
		test(asList(1, 2, 3, 4, 5));
		test(asList(1, 2, 3, 4, 5, 6));
		test(asList(1, 2, 3, 4, 5, 6, 7, 8));
		test(asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
		test(asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 9));
		test(asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9));
		test(asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 9));	
		test(asList(Utils.createIntArray1D(1, 13, 1)));
	}
	
	private void test(ListNode head) {
		Solution s = new Solution();
		com.lsa.letcode.the108.sortedArrToBst.Solution s1 = new com.lsa.letcode.the108.sortedArrToBst.Solution();
		TreeNode bstFromList = s.sortedListToBST(head);
//		int[] inorder2 = Ints.toArray(TreeUtils.inorder(bstFromArr));
//		assertTrue(Arrays.equals(inorder, inorder2));
//		System.out.println(Arrays.toString(toArray(head)));
//		TreeNode sortedArrayToBST = s1.sortedArrayToBST(toArray(head));
		Node<Integer> t1 = TreeUtils.copyAdaptTree(bstFromList);
//		Node<Integer> t2 = TreeUtils.copyAdaptTree(sortedArrayToBST);
//		System.out.println("-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=");
//		System.out.println(String.format("<<<< %s >>>>", TreeUtils.maxDepthRec(bstFromList)));
//		System.out.println(BinaryTreeUtils.toString(t1));
//		assertTrue(TreeUtils.areEqual(sortedArrayToBST, bstFromList));
//		assertTrue(BinaryTreeUtils.isBst(IntegerComparator.instance(), t2, inorder[0], inorder[inorder.length - 1]));
	}
}
